package MyList;


import java.util.Arrays;

public class MyArrayList implements IList{

    private int[] elems;
    private int usedSize = 0;
    public final int DEFAULT_SIZE = 10;

    public MyArrayList (){
        elems = new int[DEFAULT_SIZE];
    }
    public MyArrayList(int capacity){
        elems = new int[capacity];
    }
    @Override
    public void add(int data) {
//        尾插法

        if (isFull()){
//            顺序表已满 要扩容
           elems = Arrays.copyOf(elems,elems.length*2);
        }
        this.elems[usedSize] = data;
        usedSize++;
    }

    @Override
    public void add(int pos, int data) {
//             在指定位置新增元素

//        首先检查下标是否合法
        if (pos < 0 || pos > usedSize){
            System.out.println("下标 不合法!");
            return;
        }
        if (isFull()){
//            顺序表已满 要扩容
            elems =  Arrays.copyOf(elems,elems.length*2);
        }
        for (int i = usedSize-1; i >= pos; i--){
            // 向后移动元素，为新元素腾出位置
            elems[i+1] = elems[i];
        }
        elems[pos] = data;
        usedSize++;
    }

    @Override
    public boolean contains(int toFind) {
//        判断是否包含某个元素
        if (usedSize == 0){
//            顺序表为空
            return false;
        }
        for (int i = 0; i < usedSize; i++) {
            if (elems[i] == toFind){
                return true;
            }
        }
        return false;
    }

    @Override
    public int indexOf(int toFind) {
        //        查找元素的对应位置
        for (int i = 0; i < usedSize; i++) {
            if (elems[i] == toFind){
                return i;
            }
        }
        return -1;//没找到
    }

    @Override
    public int get(int pos) {
        // 获取 pos 位置的元素
       if (pos < 0 || pos >= usedSize){
           return -1;//非法位置
       }
       int n = elems[pos];
       return n;
    }

    @Override
    public void set(int pos, int value) {
// 给 pos 位置的元素设为 value
        if (pos < 0 || pos >= usedSize){
            System.out.println("非法位置!");
            return ;//非法位置`
        }
        elems[pos] = value;
    }

    @Override
    public void remove(int toRemove) {
//    删除第一次出现的关键字key
        if (usedSize == 0){
            System.out.println("顺序表为空!");
            return;
        }
        for (int i = 0; i < usedSize; i++) {
            if (elems[i] == toRemove){
//               找到了要删除的 key
                for(int j = i; j < usedSize-1 ;j++){
                    //从后往前覆盖
                    elems[j] = elems[j+1];
                }
                usedSize--;
                return;
            }
        }
        System.out.println("元素未找到!");
    }

    @Override
    public int size() {
//        顺序表长度
        return usedSize;
    }

    @Override
    public void clear() {
//       清空顺序表
        usedSize = 0;
    }

    @Override
    public void display() {
//        展示顺序表中的元素
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elems[i]+" ");
        }
        System.out.println();
    }

    @Override
    public boolean isFull() {
        return usedSize == elems.length;
    }

//    轮转数组     力扣189
//    思路: 先全部翻转  然后根据k 反转这两区间
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums,0,nums.length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);

    }
    /*
     * @param num:
	 * @param start:
	 * @param end:
     * @return void
            * @author: Jovan
            * @description:
     * @date: 2024/7/19 17:49
     */

    public void reverse(int[] num, int start,int end){
        while(start < end){
            int temp = num[start];
            num[start] = num[end];
            num[end] = temp;
            start++;
            end--;
        }
    }

//    数组逆序
    public void reverse1(int[] n){
        int num = n.length;
        for (int i = 0; i < num/2; i++) {
            int temp = n[i];
            n[i] = n[num-1-i];
            n[num-1-i] = temp;
        }
        for (int i = 0; i < num; i++) {
            System.out.printf(n[i]+" ");
        }
    }


    public void reverse2(int[] n){
        int start = 0;
        int end = n.length-1;
        while(start < end){
            int temp = n[start];
            n[start] = n[end];
            n[end] = temp;
            start++;
            end--;
        }
        for (int i = 0; i < n.length; i++) {
            System.out.printf(n[i]+" ");
        }
    }


    public  void rotate1(int[] nums, int k){
         k %= nums.length;
        reverse(nums,0,nums.length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);
    }

}
